/*
 * @lc app=leetcode.cn id=69 lang=java
 *
 * [69] x 的平方根 
 */

// @lc code=start
class Solution {
    /**
     * Accepted
    1017/1017 cases passed (1 ms)
    Your runtime beats 93.72 % of java submissions
    Your memory usage beats 59.68 % of java submissions (38.7 MB)
     */
    public int mySqrt(int x) {
        if (x < 2)
            return x;
        int l = 0, r = x, res = 0;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (mid <= x / mid) {
                res = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return res;
    }
}
// @lc code=end
